package com.xhj.joffer.array;

import org.junit.Test;

import java.util.*;

/** @author haijianxia pure_xhj@163.com @Date 2021-09-01 @Time 17:55 */
public class TwoArrayContainsNum {
  public static void main(String[] args) {

    int[][] two2 = new int[7][9];
    for (int i = 0; i < two2.length; i++) {
      for (int j = 0; j < two2[i].length; j++) {
        two2[i][j] = 0;
      }
    }

    two2 = createArray(two2);
    for (int i = 0; i < two2.length; i++) {
      System.out.println(Arrays.toString(two2[i]));
    }

    boolean result = false;
    int target = 14;

    //    result = test01(two, num);
    //    result = test02fail(two2, target);
    //    result=test03(two2, target);
    result = test05(two2, target);

    System.out.println("result = " + result);
  }
  /** @return */
  @Test
  public static boolean test01(int[][] matrix, int target) {
    System.out.println("=============test01==============");
    System.out.println("");
    long time01 = System.currentTimeMillis();

    boolean result = false;
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix[i].length; j++) {
        if (target == matrix[i][j]) {
          result = true;
          return result;
        }
      }
    }
    long time0101 = System.currentTimeMillis() - time01;
    System.out.println("\ntest01 耗时 =  " + time0101 + "ms");
    System.out.println("=================================");

    return result;
  }
  /** 夹逼 */
  @Test
  public static boolean test02fail(int[][] matrix, int target) {
    System.out.println("=============test02==============");
    System.out.println("夹逼");
    long time02 = System.currentTimeMillis();

    boolean result = false;

    int leftI = 0, leftJ = 0, rightI = matrix.length - 1, rightJ = matrix[0].length - 1;
    int midI = -1, midJ = -1; // 默认每行列数相等
    // mid=(left+right)/2
    // mid-value>target,  left=left,right=mid
    // mid-value<target,  left=mid,right=right
    // mid-value=target,  true
    // mid=left,  if mid=target|right=mid true, else false
    do {
      midI = (leftI + rightI) / 2;
      midJ = (leftI + rightI) / 2;
      if (matrix[midI][midJ] == target) {
        result = true;
        break;
      }
      // 最后剩余两个值待比较
      if (midI == leftI && midJ == leftJ) {
        if (matrix[rightI][rightJ] == target) {
          result = true;
          //          break;
        }
      }
      // 夹逼
      if (matrix[midI][midJ] > target) {
        rightI = midI;
        rightJ = midJ;
      } else if (matrix[midI][midJ] < target) {
        leftI = midI;
        leftJ = midJ;
      }
    } while (midI != leftI && midJ != leftJ);

    long time0202 = System.currentTimeMillis() - time02;
    System.out.println("\ntest02 耗时 =  " + time0202 + "ms");
    System.out.println("=================================");

    return result;
  }
  /** 二维转一维, 夹逼 */
  @Test
  public static boolean test03(int[][] two, int target) {
    System.out.println("=============test03==============");
    System.out.println("二维转一维, 夹逼");
    long time03 = System.currentTimeMillis();

    boolean result = false;

    // list<map<下标,值>>
    ArrayList<String> list = new ArrayList<>();
    for (int i = 0; i < two.length; i++) {
      for (int j = 0; j < two[i].length; j++) {
        list.add("" + i + ":" + j + ":" + two[i][j]);
      }
    }
    // fail ...  合并之后不一定有序了
    //    [6, 11, 19, 27, 30, 33, 35, 35, 44]
    //    [14, 14, 26, 36, 45, 46, 55, 62, 70]
    //    [20, 25, 35, 45, 53, 60, 64, 64, 70]

    long time0303 = System.currentTimeMillis() - time03;
    System.out.println("\ntest03 耗时 =  " + time0303 + "ms");
    System.out.println("=================================");

    return result;
  }

  /** 创建有序数组 */
  @Test
  public static int[][] createArray(int[][] two) {
    System.out.println("=============test99==============");
    System.out.println("创建有序数组");
    long time99 = System.currentTimeMillis();

    Random random = new Random();
    int i1 = random.nextInt(10);
    int temp = i1;
    for (int i = 0; i < two.length; i++) {
      for (int j = 0; j < two[i].length; j++) {
        // 非首行
        if (i != 0) {
          if (j != 0) { // 非首列
            two[i][j] =
                two[i - 1][j] > two[i][j - 1]
                    ? two[i - 1][j] + random.nextInt(10)
                    : two[i][j - 1] + random.nextInt(10);
          } else {
            two[i][j] = two[i - 1][j] + random.nextInt(10);
          }
          // 首行
        } else {
          if (j != 0) { // 非首列
            two[i][j] = two[i][j - 1] + random.nextInt(10);
          } else {
            two[i][j] = random.nextInt(10);
          }
        }
      }
    }

    long time9999 = System.currentTimeMillis() - time99;
    System.out.println("\ntest99 耗时 =  " + time9999 + "ms");
    System.out.println("=================================");

    return two;
  }
  /** 夹逼 1.确定行 2.确定列 */
  @Test
  public static boolean test05(int[][] matrix, int target) {
    System.out.println("=============test05==============");
    System.out.println("夹逼");
    long time05 = System.currentTimeMillis();

    boolean result = false;

    int row = 0; // - - - - - - -确定行
    //     left>target || right<target
    //     if target in(l r){
    //       if r-l>1 {
    //           mid=target return row-0
    //            < l=mid if r-l>1 ……
    //            > r=mid if  ……
    //       }  else row=l
    //     }else mid{
    //     }
    //    matrix[i][0]
    int left = 0, right = matrix.length - 1, mid = (left + right) / 2;
    for (int i = 0; i < matrix.length; i++) {
      if (matrix[left][0] > target /*|| matrix[right][matrix[right].length] < target*/) {
        return false;
      } else {

        if (matrix[left][0] == target) {
          return true;
        }
        if (matrix[left][0] < target) {
          return true;
        }
      }
    }
    System.out.println("row = " + row);
    int colomn = 0; // - - - - - - -确定列
    for (int i = 0; i < matrix[row].length; i++) {
      if (matrix[row][i] == target) {
        System.out.println("i = " + i);
        result = true;
      }
    }

    long time0505 = System.currentTimeMillis() - time05;
    System.out.println("\ntest05 耗时 =  " + time0505 + "ms");
    System.out.println("=================================");

    return result;
  }
}
